% !TEX root = TMV_Documentation.tex

\section{Upper/lower triangle matrices}
\index{UpperTriMatrix}
\index{LowerTriMatrix|see{UpperTriMatrix}}
\label{TriMatrix}

The \tt{UpperTriMatrix} class is our upper triangle matrix class, which is non-zero
only on the main diagonal and above.  \tt{LowerTriMatrix} is our class for lower
triangle matrices, which are non-zero only on the main diagonal and below.

The class \tt{UpperTriMatrix} inherits from \tt{GenUpperTriMatrix}, 
and the class \tt{LowerTriMatrix}
inherits from \tt{GenLowerTriMatrix}, both of
which in turn inherit from \tt{BaseMatrix}.  
The various views and composite classes described below
also inherit from \tt{GenUpperTriMatrix} and \tt{GenLowerTriMatrix} 
as appropriate.
\index{UpperTriMatrix!UpperTriMatrixView}
\index{UpperTriMatrix!ConstUpperTriMatrixView}
\index{UpperTriMatrix!GenUpperTriMatrix}
\index{UpperTriMatrix!UpperTriMatrixComposite}
\index{BaseMatrix}

In addition to the \tt{T} template parameter, there are three other template 
parameters:
\tt{dt}, which can be either \tt{tmv::UnitDiag} or \tt{tmv::NonUnitDiag};
\tt{stor}, which can be \tt{tmv::RowMajor} or \tt{tmv::ColMajor};
and \tt{index}, which can be \tt{tmv::CStyle} or \tt{tmv::FortranStyle}.
The default values for these template parameters are 
\tt{NonUnitDiag}, \tt{ColMajor}, and \tt{CStyle} respectively.

The storage of both an \tt{UpperTriMatrix} and a \tt{LowerTriMatrix} takes
$N \times N$ elements of memory, even though approximately half of them 
are never used.  Someday, I'll write the packed storage versions, which allow for
efficient storage of the matrices.

All of the routines are analogous for \tt{UpperTriMatrix} and 
\tt{LowerTriMatrix}, so we only list each routine once 
(the \tt{UpperTriMatrix} version for
definiteness).  

Most functions and methods for \tt{UpperTriMatrix} and \tt{LowerTriMatrix}
work the same as they do for \tt{Matrix}.
In these cases, we will just list the functions that are allowed with the
effect understood to be the same as for a regular \tt{Matrix}.  Of course, there are 
almost always algorithmic speed-ups, which the code will use to take advantage of the 
triangle structure.
Whenever there is a difference in how a function works,
we will explain the difference.

\subsection{Constructors}
\index{UpperTriMatrix!Constructors}
\label{TriMatrix_Constructors}

\begin{itemize}
\item 
\begin{tmvcode}
tmv::UpperTriMatrix<T,dt,stor,index> U(size_t n)
\end{tmvcode}
Makes an \tt{n} $\times$ \tt{n} \tt{UpperTriMatrix} with \underline{uninitialized} values.
If debugging is turned on (i.e. not turned off
with \tt{-DNDEBUG} or \tt{-DTMVNDEBUG}), then the values are in fact initialized to 888.  

\item
\begin{tmvcode}
tmv::UpperTriMatrix<T,dt,stor,index> U(size_t n, T x)
\end{tmvcode}
Makes an \tt{n} $\times$ \tt{n} \tt{UpperTriMatrix} with all values equal to \tt{x}.

\item
\begin{tmvcode}
tmv::UpperTriMatrix<T,dt,stor,index> U(size_t n, const T* vv)
tmv::UpperTriMatrix<T,dt,stor,index> U(size_t n, 
      const std::vector<T>& vv)
\end{tmvcode}
Makes an \tt{UpperTriMatrix} which copies the elements of \tt{vv}.
Note: the elements in \tt{vv} need to include the zero's of the lower triangle 
portion of \tt{U}.

\item 
\begin{tmvcode}
tmv::UpperTriMatrix<T,dt,stor,index> U(const GenMatrix<T>& m)
tmv::UpperTriMatrix<T,dt,stor,index> U(const GenUperTriMatrix<T>& U2)
\end{tmvcode}
Make an \tt{UpperTriMatrix} which copies the corresponding values of
\tt{U2}.  Note that the second one is allowed to have \tt{U2} be
\tt{NonUnitDiag} but \tt{dt = UnitDiag}, in which case only the 
off-diagonal elements are copied.  The converse would set the 
diagonal of the new \tt{UpperTriMatrix} to all 1's.

\item
\begin{tmvcode}
tmv::UpperTriMatrix<T> U1(const GenUpperTriMatrix<T2>& U2)
U1 = U2
\end{tmvcode}
Copy the \tt{UpperTriMatrix U2}, which may be of any type \tt{T2} so long
as values of type \tt{T2} are convertible into type \tt{T}.
The assignment operator has the same flexibility.

\item
\begin{tmvcode}
tmv::UpperTriMatrixView<T,index> U = 
      tmv::UpperTriMatrixViewOf(T* vv, size_t n, 
      StorageType stor, DiagType dt=NonUnitDiag)
tmv::ConstUpperTriMatrixView<T,index> U = 
      tmv::UpperTriMatrixViewOf(const T* vv, size_t n, 
      StorageType stor, DiagType dt=NonUnitDiag)
\end{tmvcode}
\index{UpperTriMatrix!View of raw memory}
Make a \tt{UpperTriMatrixView} of the actual memory elements, \tt{vv}.
One wrinkle here is that if \tt{dt} is \tt{UnitDiag}, then 
\tt{vv} is still the location of the
upper left corner, even though that value is never used 
(since the value is just taken to
be 1).  Also, \tt{vv} must be of length \tt{n} $\times$ \tt{n},
so all of the lower triangle
elements must be in memory, even though they are never used.

\end{itemize}

\subsection{Access}
\index{UpperTriMatrix!Access methods}
\label{TriMatrix_Access}

\begin{tmvcode}
U.resize(size_t newsize)
\end{tmvcode}
\index{UpperTriMatrix!Methods!resize}

\begin{tmvcode}
U.nrows() = U.ncols() = U.colsize() = U.rowsize() = U.size()
U(i,j)
U.row(int i, int j1, int j2)
U.col(int i, int j1, int j2)
U.diag()
U.diag(int i)
U.diag(int i, int k1, int k2)
\end{tmvcode}
\index{UpperTriMatrix!Methods!nrows}
\index{UpperTriMatrix!Methods!ncols}
\index{UpperTriMatrix!Methods!rowsize}
\index{UpperTriMatrix!Methods!colsize}
\index{UpperTriMatrix!Methods!size}
\index{UpperTriMatrix!Methods!operator()}
\index{UpperTriMatrix!Methods!row}
\index{UpperTriMatrix!Methods!col}
\index{UpperTriMatrix!Methods!diag}
For the mutable \tt{d(i,j)} version, 
Note that the versions of \tt{row} and \tt{col} with only one argument are
missing, since the full row or column isn't accessible as a \tt{VectorView}.
You must specify a valid range within the row or column that you want, 
given the upper triangle shape of \tt{U}.  Likewise for the \tt{LowerTriMatrix}
versions of these.
If \tt{dt} is \tt{UnitDiag}, then the range may not include the diagonal element.
Similarly, \tt{U.diag()} is valid only if \tt{dt} is \tt{NonUnitDiag}.

\begin{tmvcode}
U.subVector(int i, int j, int istep, int jstep, int size)
U.subMatrix(int i1, int i2, int j1, int j2)
U.subMatrix(int i1, int i2, int j1, int j2, int istep, int jstep)
\end{tmvcode}
\index{UpperTriMatrix!Methods!subVector}
\index{UpperTriMatrix!Methods!subMatrix}
This works the same as for \tt{Matrix}
(See \ref{Matrix_Access}),
except that all of the elements in the 
subvector or submatrix must be completely within the upper or lower triangle, as
appropriate.  If \tt{dt} is \tt{UnitDiag}, then no elements may be on the 
main diagonal.

\begin{tmvcode}
U.subTriMatrix(int i1, int i2, int istep = 1)
\end{tmvcode}
\index{UpperTriMatrix!Methods!subTriMatrix}
This returns the upper or lower triangle matrix whose upper-left
corner is \tt{U(i1,i1)}, and whose lower-right corner is 
\tt{U(i2-istep,i2-istep)} for C-style indexing or \tt{U(i2,i2)} 
for Fortran-style indexing.  If \tt{istep} $\neq 1$, then it is the 
step in both the \tt{i} and \tt{j} directions.

\begin{tmvcode}
U.offDiag()
\end{tmvcode}
\index{UpperTriMatrix!Methods!offDiag}
This returns a view to the portion of the triangle matrix that does not include
the diagonal elements.  It will always be \tt{NonUnitDiag}.
Internally, it provides an easy way to deal with the \tt{UnitDiag} triangle matrices
for many routines.  But it may be useful for some users as well.

\begin{tmvcode}
U.viewAsUnitDiag()
\end{tmvcode}
\index{UpperTriMatrix!Methods!viewAsUnitDiag}
This returns a view to a \tt{NonUnitDiag} triangle matrix that treats it
instead as a \tt{UnitDiag} triangle matrix.

\begin{tmvcode}
U.transpose()
U.conjugate()
U.adjoint()
U.view()
U.cView()
U.fView()
U.realPart()
U.imagPart()
\end{tmvcode}
\index{UpperTriMatrix!Methods!transpose}
\index{UpperTriMatrix!Methods!conjugate}
\index{UpperTriMatrix!Methods!adjoint}
\index{UpperTriMatrix!Methods!view}
\index{UpperTriMatrix!Methods!cView}
\index{UpperTriMatrix!Methods!fView}
\index{UpperTriMatrix!Methods!realPart}
\index{UpperTriMatrix!Methods!imagPart}
Note that the transpose and adjoint of an \tt{UpperTriMatrix} is an
\tt{LowerTriMatrixView} and vice versa.
\vspace{12pt}

\subsection{Functions}
\index{UpperTriMatrix!Functions of}
\label{TriMatrix_Functions}

\begin{tmvcode}
RT U.norm1() = Norm1(U)
RT U.norm2() = Norm2(U) = U.doNorm2()
RT U.normInf() = NormInf(U)
RT U.normF() = NormF(U) = U.norm() = Norm(U)
RT U.normSq() = NormSq(U)
RT U.normSq(RT scale)
RT U.maxAbsElement() = MaxAbsElement(U)
RT U.maxAbs2Element() = MaxAbs2Element(U)
T U.trace() = Trace(U)
T U.sumElements() = SumElements(U)
RT U.sumAbsElements() = SumAbsElements(U)
RT U.sumAbs2Elements() = SumAbs2Elements(U)
T U.det() = Det(U)
RT U.logDet(T* sign=0) = LogDet(U)
bool U.isSingular()
RT U.condition()
RT U.doCondition()
Uinv = U.inverse() = Inverse(U)
U.makeInverse(Matrix<T>& minv)
U.makeInverse(UpperTriMatrix<T>& Uinv)
U.makeInverseATA(Matrix<T>& cov)
\end{tmvcode}
\index{UpperTriMatrix!Functions of!Norm1}
\index{UpperTriMatrix!Functions of!Norm2}
\index{UpperTriMatrix!Functions of!NormInf}
\index{UpperTriMatrix!Functions of!MaxAbsElement}
\index{UpperTriMatrix!Functions of!MaxAbs2Element}
\index{UpperTriMatrix!Methods!norm1}
\index{UpperTriMatrix!Methods!norm2}
\index{UpperTriMatrix!Methods!doNorm2}
\index{UpperTriMatrix!Methods!normInf}
\index{UpperTriMatrix!Methods!maxAbsElement}
\index{UpperTriMatrix!Methods!maxAbs2Element}
\index{UpperTriMatrix!Functions of!Norm}
\index{UpperTriMatrix!Functions of!NormF}
\index{UpperTriMatrix!Functions of!NormSq}
\index{UpperTriMatrix!Functions of!Trace}
\index{UpperTriMatrix!Functions of!SumElements}
\index{UpperTriMatrix!Functions of!SumAbsElements}
\index{UpperTriMatrix!Functions of!SumAbs2Elements}
\index{UpperTriMatrix!Functions of!Det}
\index{UpperTriMatrix!Functions of!LogDet}
\index{UpperTriMatrix!Functions of!Inverse}
\index{UpperTriMatrix!Methods!norm}
\index{UpperTriMatrix!Methods!normF}
\index{UpperTriMatrix!Methods!normSq}
\index{UpperTriMatrix!Methods!trace}
\index{UpperTriMatrix!Methods!sumElements}
\index{UpperTriMatrix!Methods!sumAbsElements}
\index{UpperTriMatrix!Methods!sumAbs2Elements}
\index{UpperTriMatrix!Methods!det}
\index{UpperTriMatrix!Methods!logDet}
\index{UpperTriMatrix!Methods!isSingular}
\index{UpperTriMatrix!Methods!condition}
\index{UpperTriMatrix!Methods!doCondition}
\index{UpperTriMatrix!Methods!inverse}
\index{UpperTriMatrix!Methods!makeInverse}
\index{UpperTriMatrix!Methods!makeInverseATA}
Since the inverse of an \tt{UpperTriMatrix} is also upper triangular,
the object returned by \tt{U.inverse()} is 
assignable to an \tt{UpperTriMatrix}.  Of course you can also assign it
to a regular \tt{Matrix} if you prefer.  Similarly, there are versions
of \tt{U.makeInverse(minv)} for both argument types.  Of course, similar statements
hold for \tt{LowerTriMatrix} as well.

\begin{tmvcode}
U.setZero()
U.setAllTo(T x)
U.addToAll(T x)
U.clip(RT thresh)
U.setToIdentity(T x = 1)
U.conjugateSelf()
U.invertSelf()
Swap(U1,U2)
\end{tmvcode}
\index{UpperTriMatrix!Methods!setZero}
\index{UpperTriMatrix!Methods!setAllTo}
\index{UpperTriMatrix!Methods!addToAll}
\index{UpperTriMatrix!Methods!clip}
\index{UpperTriMatrix!Methods!setToIdentity}
\index{UpperTriMatrix!Methods!conjugateSelf}
\index{UpperTriMatrix!Methods!invertSelf}
\index{UpperTriMatrix!Functions of!Swap}
Like for \tt{DiagMatrix}, \tt{invertSelf} calculates $U^{-1}$ in place.  
It is equivalent to \tt{U = U.inverse()} and, like the other division operations, is invalid for \tt{T = int} or \tt{complex<int>}.
\vspace{12pt}

\subsection{Arithmetic}
\index{UpperTriMatrix!Arithmetic}
\label{TriMatrix_Arithmetic}

In addition to \tt{x}, \tt{v}, and \tt{m} from before, 
we now add \tt{U} and \tt{L} for a \tt{UpperTriMatrix}
and \tt{LowerTriMatrix} respectively.  Where the syntax is identical
for the two cases, only the \tt{U} form is listed.

\begin{tmvcode}
U2 = -U1
U2 = x * U1
U2 = U1 [*/] x
U3 = U1 [+-] U2
m2 = m1 [+-] U
m2 = U [+-] m1
m = L [+-] U
m = U [+-] L
U [*/]= x
U2 [+-]= U1
m [+-]= U
v2 = U * v1
v2 = v1 * U
v *= U
U3 = U1 * U2
m2 = U * m1
m2 = m1 * U
m = U * L
m = L * U
U2 *= U1
m *= U
U2 = U1 [+-] x
U2 = x [+-] U1
U [+-]= x
\end{tmvcode}

\subsection{Division}
\index{UpperTriMatrix!Arithmetic!division}
\label{TriMatrix_Division}

The division operations are: (again omitting the L forms when redundant)
\begin{tmvcode}
v2 = v1 [/%] U
m2 = m1 [/%] U
m2 = U [/%] m1
U3 = U1 [/%] U2
U2 = x [/%] U1
m = U [/%] L
m = L [/%] U
v [/%]= U
U2 [/%]= U1
m [/%]= U
\end{tmvcode}

There is only one allowed \tt{DivType} for an \tt{UpperTriMatrix} or a 
\tt{LowerTriMatrix}: \tt{LU}.
And, since it is also the default behavior,
there is no reason to ever specify it.
Furthermore, as with a \tt{DiagMatrix},
the decomposition requires no work at all.  In fact, the ease of dividing by a 
upper or lower triangle matrix is precisely why the LU decomposition is useful.
Hence, it is always done in place.  i.e. no extra storage is needed, and all of
the \tt{m.divideInPlace()}, \tt{m.saveDiv()}, etc. are irrelevant.

If an \tt{UpperTriMatrix} or \tt{LowerTriMatrix} is singular, 
you can check easily with \tt{m.isSingular()},
but there is no direct way to use SVD for the division and avoid any
divisions by 0.  If you want to do this use \tt{BandMatrixViewOf(m)} to 
treat the \tt{TriMatrix} as a \tt{BandMatrix}, which can use SVD.

\subsection{Input/Output}
\index{UpperTriMatrix!Input/output}
\label{TriMatrix_IO}

The simplest output is the usual:
\begin{tmvcode}
os << U << L
\end{tmvcode}
where \tt{os} is any \tt{std::ostream}.
The output format is the same as for a \tt{Matrix}, including all the 0's.
(See \ref{Matrix_IO}.)

There is also a compact format.  For an \tt{UpperTriMatrix},
\begin{tmvcode}
U.writeCompact(os)
\end{tmvcode}
\index{UpperTriMatrix!Methods!writeCompact}
outputs in the format:
\begin{tmvcode}
U n 
( U(0,0)  U(0,1)  U(0,2)  ...  U(0,n-1) )
( U(1,1)  U(1,2)  ...  U(1,n-1) )
...
( U(n-1,n-1) )
\end{tmvcode}
For a \tt{LowerTriMatrix},
\begin{tmvcode}
L.writeCompact(os)
\end{tmvcode}
outputs in the format:
\begin{tmvcode}
L n 
( L(0,0) )
( L(1,0)  L(1,1) )
...
( L(n-1,0)  L(n-1,1) ... L(n-1,n-1) )
\end{tmvcode}

In each case, the compact format can be read back in the usual two ways:
\begin{tmvcode}
tmv::UpperTriMatrix<T> U(n);
tmv::LowerTriMatrix<T> L(n);
is >> U >> L;
std::auto_ptr<tmv::UpperTriMatrix<T> > Uptr;
std::auto_ptr<tmv::LowerTriMatrix<T> > Lptr;
is >> Uptr >> Lptr;
\end{tmvcode}

One can write small values as 0 with
\begin{tmvcode}
m.write(std::ostream& os, RT thresh)
m.writeCompact(std::ostream& os, RT thresh)
\end{tmvcode}
\index{UpperTriMatrix!Methods!write}
\index{UpperTriMatrix!Methods!writeCompact}

